<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    // 题目: https://leetcode-cn.com/problems/number-of-recent-calls/

    // TODO: 分析
    // 分别在 1ms 100ms 3001ms 3002ms 这四个时刻发出四个请求
    // 需要返回过去 3000ms 内发生的所有请求数（包括新请求, 确切地说, 返回范围在 [t-3000, t] 内发生的请求数)
    // requests = [1], 范围是 [-2999,1]
    // requests = [1, 100], 范围是 [-2900,100]
    // requests = [1, 100, 3001], 范围是 [1,3001]
    // requests = [1, 100, 3001, 3002], 范围是 [2,3002]
    // 即: 越早发出的请求越早不在最近 3000ms 内的请求里, 满足先进先出, 考虑用队列

    // TODO: 解题步骤: 有新请求就入队, 将 3000ms 前发出的请求移出队列, 队列的长度就是最近的请求次数


    // 时间复杂度: 有个 while 循环, 即 O(n), n 为需要被移出的请求个数
    // 空间复杂度: 有个队列(数组 -> this.q), 即 O(n), n 为最近的请求次数
    var RecentCounter = function () {
      this.q = [];
    }

    RecentCounter.prototype.ping = function (t) {
      // 每发一次请求, 入队
      this.q.push(t);

      // 移出不在时间内的老请求
      // 判断队头是否小于 t - 3000
      while(this.q[0] < t - 3000) {
        this.q.shift();
      }

      return this.q.length;
    }

    var counter = new RecentCounter();
    counter.ping(1);
    counter.ping(100);
    counter.ping(3001);
    counter.ping(3002);

    console.log(counter.q);
  </script>
</body>
</html>